U.S. Pat. No. 6,564,361 granted May 13, 2003 to Andrej A. Zolotykh et al. for “Method and Apparatus for Timing Driven Resysthesis” and assigned to the same assignee as the present invention, describes techniques for optimizing integrated circuit (IC) designs employing local optimization. Local logic restructuring is a basic step of the resynthesis procedure. One such logic restructuring procedure is described in U.S. Pat. No. 6,543,032 granted Apr. 1, 2003 to Andrej A. Zolotykh et al. for “Method and Apparatus for Local Resynthesis of Logic Trees with Multiple Cost Functions” and assigned to the same assignee as the present invention. The input of the local logic restructuring procedure described in the U.S. Pat. No. 6,543,032 is a logical tree. The result of the local logic restructuring procedure is a new logical tree that is equivalent to the initial tree.
U.S. Pat. No. 6,513,148 granted Jan. 28, 2003 to Elyar E. Gasanov et al. for “Density Driven Assignment of Coordinates” and assigned to the same assignee as the present invention describes a procedure to assign coordinates to nodes of a new logical tree. But the procedure described in the U.S. Pat. No. 6,513,148 leads to increased summary wire length if the resynthesis stage is the area optimization.
IC chips generally comprise a plurality of cells. Each cell may include one or more circuit elements, such as transistors, capacitors and other basic circuit elements, which are interconnected in a standardized manner to perform a specific function.
The timing driven resynthesis described in the U.S. Pat. No. 6,564,361 patent has been used to change the chip design step by step, making the improvements of the chip locally. The main concept of the local resynthesis is to consecutively examine the cell trees of a chip for the necessity of the optimization, and then organize the chosen trees as local tasks for the resynthesis that follows. All necessary information about the tree neighborhood (neighboring cells, capacities, delays, etc.) is first collected. Next, local optimization procedures work with this information only. No additional information about the chip structure is required.
Within the logical resynthesis, ordinary logical cells are considered, i.e. those cells with one output pin constructed using standard logical gates NOT, AND, OR. A logical tree is a tree formed from ordinary logical cells. Inside a logical tree, the output pin of each cell, other than the root (or root cell), is connected to exactly one other input pin, and this one other input pin is a pin of a cell of the logical tree. In contrast, the output pin of the root may be connected to any number of cell input pins. All cells connected with the output pin of the root of a tree may not belong to the tree, and the cells are not necessarily logical. An input pin of a cell of the tree may be connected to the power or the ground, or to a cell outside the tree. The cell input pin may be called the entrances of the tree.
FIG. 1 illustrates an exemplary logical tree that includes six cells inside rectangle 50. All entrances of the tree are enumerated by assigning variables xn to the entrances. In addition, identical variables may be assigned to entrances connected through a wire because the input values of these entrances are always the same. As shown, for example, the variable x1 is assigned to the first input pin of the cell ND3C and to the first input pin of the cell ENB, the variable x2 is assigned to the second input pin of the cell ENB and to the first input pin of the cell NR2A, the variable x3 is assigned to the input pin of the cell N1C.
One goal of the logical resynthesis is to change a logical tree into a logically equivalent one, which is better with respect to a given estimator. The nodes of the initial logical tree have the coordinates, but it is necessary to assign coordinates to nodes of new logical tree.
The present invention is directed the assignment of coordinates to nodes of a new logical tree without increasing summary wire length or wire congestion.